524. Longest Word in Dictionary through Deleting

1. Question

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

2. Examples

Example 1:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Example 2:

Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"

3. Constraints

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s and dictionary[i] consist of lowercase English letters.

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

compareTo() 方法用于两种方式的比较：

• 字符串与对象进行比较。

• 按字典顺序比较两个字符串。

• 如果参数字符串等于此字符串，则返回值 0；

• 如果此字符串小于字符串参数，则返回一个小于 0 的值；

• 如果此字符串大于字符串参数，则返回一个大于 0 的值。

• 如果第一个字符和参数的第一个字符不等，结束比较，返回第一个字符的ASCII码差值。

  如果第一个字符和参数的第一个字符相等，则以第二个字符和参数的第二个字符做比较，以此类推,直至不等为止，返回该字符的ASCII码差值。 如果两个字符串不一样长，可对应字符又完全一样，则返回两个字符串的长度差值。

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String ans = "";
        dictionary.sort((o1, o2) -> {
            if (o1.length() != o2.length()) {
                return o2.length() - o1.length();
            }
            return o1.compareTo(o2);
        });

        // dictionary.forEach(System.out::println);

        for (String str : dictionary) {
            int p1 = 0;
            int p2 = 0;
            while (p1 < s.length() && p2 < str.length()) {
                if (s.charAt(p1) == str.charAt(p2)) {
                    p1++;
                    p2++;
                } else {
                    p1++;
                }
            }
            if (p2 == str.length()) {
                ans = str;
                break;
            }
        }
        return ans;
    }
}